{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### compile-time вычисления"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### before C++11"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Все compile-time вычисления основаны на типах, что больше похоже на метапрограммирование."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Посчитаем факториал во время копиляции:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template<unsigned N>\n",
    "struct Factorial\n",
    "{\n",
    "    static const int value = N * Factorial<N - 1>::value;\n",
    "};\n",
    "\n",
    "template<>\n",
    "struct Factorial<0>\n",
    "{\n",
    "    static const int value = 1;\n",
    "};\n",
    "\n",
    "int main()\n",
    "{\n",
    "    return Factorial<10>::value + Factorial<3>::value;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопрос**: сколько будет создано структур `Factorial` компилятором?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C++11"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В С++11 появляется слово `cosntexpr` и возможность делать `constexpr`-функции. Однако, функционал ограничен:\n",
    "\n",
    "* Функция возвращать и принимать может только [literal-типы](https://en.cppreference.com/w/cpp/named_req/LiteralType)\n",
    "* Функция может иметь только один `return` (и никаких локальных переменных, циклов ...)\n",
    "* Функция может вызывать только `constexpr`-функции\n",
    "* Функция может кинуть исключение, чтобы сообщить компилятору, что произошла ошибка."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "constexpr int factorial(int n)\n",
    "{\n",
    "    return n < 0 ? throw std::out_of_range(\"\")\n",
    "                 : n == 0 ? 1\n",
    "                          : n * factorial(n - 1);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Не очень богатый набор возможностей.\n",
    "\n",
    "Тем не менее, нужно усвоить понятие контекста выполнения `constexpr`-функции: runtime vs compiletime."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "int main(int argc, char **argv)\n",
    "{\n",
    "    // значение |argc| неизвестно на этапе компиляции,\n",
    "    // поэтому компилятор не может посчитать результат\n",
    "    // заранее, выполнение будет происходить в runtime\n",
    "    std::cout << factorial(argc);\n",
    "    \n",
    "    // значение |const_value| известно на этапе\n",
    "    // компиляции, поэтому компилятор может вычислить\n",
    "    // результат заранее и подставить ответ, но, емнип,\n",
    "    // не обязан (likely compiletime)\n",
    "    int const_value = 5;\n",
    "    std::cout << factorial(const_value);\n",
    "    \n",
    "    // программист обязывает компилятор вычислить результат\n",
    "    // на этапе компиляции, если компилятор не справляется,\n",
    "    // компиляция должна закончится с ошибкой (compiletime)\n",
    "    constexpr int f1 = factorial(5);\n",
    "    std::cout << f1;\n",
    "    \n",
    "    // ключевое слово volatile отключает оптимизацию,\n",
    "    // позволяющую компилятору использовать значение\n",
    "    // |const_value_2| во время компиляции. Результат\n",
    "    // будет вычиляться в runtime.\n",
    "    volatile int const_value_2 = 8;\n",
    "    std::cout << factorial(const_value_2);\n",
    "    \n",
    "    // использование результата в compiletime контексте\n",
    "    // тоже обязывает компилятор произвести вычисления\n",
    "    // compiletime\n",
    "    std::array<int, factorial(5)> arr = {};\n",
    "    static_assert(factorial(2) == 2, \"factorial(2) should be equal to 2\");\n",
    "    \n",
    "    // ошибка компиляции:\n",
    "    constexpr int f2 = factorial(argc);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечание**:\n",
    "* Переменная, объявленная `constexpr`, получает модификатор `const`.\n",
    "    * Т.о. следующий сценарий невозможен: инициализацию переменной просчитать в compiletime, а в runtime её модифицировать.\n",
    "    * В С++20 добавили такую возможность.\n",
    "* Компилятор при вычислении `constexpr`-функций *интерпретирует* код (с кучей проверок), а значит сами вычисления медленные. Насколько и как живут с этим компиляторы - чуть позднее."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### constexpr vs undefined behavior"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Приятной особенностью `constexpr`-функций является возможность находить Undefined Behavior компилятором:\n",
    "* Компилятор исполняет код, а кто лучше него знает, сейчас исполняется UB или не UB?\n",
    "* UB в compiletime-контексте - ошибка компиляции"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "constexpr int factorial(int n)\n",
    "{\n",
    "    return n < 0 ? throw std::out_of_range(\"\")\n",
    "                 : n == 0 ? 1\n",
    "                          : n * factorial(n - 1);\n",
    "}\n",
    "\n",
    "int main(int argc, char **argv)\n",
    "{\n",
    "    // ошибка компиляции, в процессе вычислений произошло\n",
    "    // переполнение знакового целого\n",
    "    constexpr int f2 = factorial(50);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Итак, у нас повился план как починить проблему UB в С++:\n",
    "1. Объявляем все функции (какие сможем) `constexpr`\n",
    "2. Полностью покрываем функции тестами, которые будут звать функции в compiletime контексте\n",
    "3. Итого: все сценарии в тестах свободны от UB."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Хорошо, но:\n",
    "* Тесты должны покрывать сценарии использования.\n",
    "    * Код `int x = ...; x * 2` при одних сценариях работает, а при других - UB. Тесты должны покрывать именно сценарии использования.\n",
    "    * Понятно, что функция `int factorial(int x)` на больших `x` будет давать UB. Вопрос в том, есть ли такие сценарии на production.\n",
    "* Набор функций, которые можно обозвать `constexpr`, не так уж и широк\n",
    "    * Над этим работает комитет"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C++14"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Расширен набор `constexpr`-функций. Тело `constexpr`-функции может содержать любые конструкции, кроме:\n",
    "* `asm`\n",
    "* `goto`\n",
    "* Переменных нелитерального типа, `static` и `thread_local`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Уже значительно лучше:\n",
    "* `asm` и `goto` редко когда нужны (почти никогда)\n",
    "* зачастую код можно организовать без `static` и `thread_local`\n",
    "* требование на литеральные типы - очень сильное, `std::vector` уже не вписывается"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Примеры:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "constexpr int factorial(int n)\n",
    "{\n",
    "    if (n < 0)\n",
    "        throw std::out_of_range(\"factorial arg < 0\");\n",
    "\n",
    "    int f = 1;\n",
    "    for (int i = 2; i <= n; ++i)\n",
    "        f *= i;\n",
    "    return f;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Если немножко подумать, то можно и так:\n",
    "\n",
    "```c++\n",
    "template<typename It, typename ValueType>\n",
    "constexpr std::size_t count(It begin, It end, const ValueType& value)\n",
    "{\n",
    "    std::size_t cnt = 0;\n",
    "    for (; begin != end; ++begin)\n",
    "        if (*begin == value)\n",
    "            ++cnt;\n",
    "    return cnt;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Вопрос:**\n",
    "    \n",
    "<details>\n",
    "<summary>Что-нибудь напоминает?</summary>\n",
    "<p>\n",
    "\n",
    "Да, стандартные алгоритмы. И их можно объявить `constexpr` и использовать в `constexpr`-функциях.\n",
    "Этим и занялся комитет, но с [С++20](https://en.cppreference.com/w/cpp/algorithm/count)\n",
    "\n",
    "</p>\n",
    "</details>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C++17 if constexpr + constexpr lambda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "constexpr lambda:\n",
    "* Теперь можно навешивать модификатор `constexpr` на лямбда-функции, а можно не навешивать:\n",
    "    > [doc](https://en.cppreference.com/w/cpp/language/lambda): constexpr: explicitly specifies that the function call operator is a constexpr function. When this specifier is not present, the function call operator will be constexpr anyway, if it happens to satisfy all constexpr function requirements\n",
    "* Лямбда-функции могут быть literal type"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Примеры:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "constexpr auto get_factorial = [](int i) {\n",
    "    if (i <= 1)\n",
    "        return 1;\n",
    "    return i * get_factorial(i - 1);\n",
    "};\n",
    "\n",
    "constexpr int a = get_factorial(5);\n",
    "\n",
    "int b = get_factorial(argc);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`if constexpr` введён как упрощение для различных механизмов С++, которые иным образом реализовывались через шаблоны или макросы.\n",
    "\n",
    "Как работает `if constexpr` на демонстрационном примере:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "template <typename T>\n",
    "auto get_value(T t) {\n",
    "    if constexpr (std::is_pointer_v<T>)\n",
    "        return *t;\n",
    "    else\n",
    "        return t;\n",
    "}\n",
    "\n",
    "// usage\n",
    "int x = 5;\n",
    "int* px = &x;\n",
    "std::cout << get_value(x);\n",
    "std::cout << get_value(px);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "При этом:\n",
    "* `get_value<int>` компилируется в `int get_value(int t) { return t; }`\n",
    "* `get_value<int*>` компилируется в `int get_value(int*t) { return *t; }`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Зачем `if constexpr` может быть полезен?\n",
    "\n",
    "Обычно всё, что реализуется через `if constexpr`, можно реализовать прежними конструкциями языка, но `if constexpr` делает это более читабельным."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример 1**: можно упростить SFINAE (на том же `get_value`).\n",
    "\n",
    "Вариант реализации `get_value` через SFINAE (вариант через доп. шаблонный параметр):\n",
    "\n",
    "\n",
    "```c++\n",
    "template <typename T,\n",
    "          std::enable_if_t<std::is_pointer<T>{}>* = nullptr>\n",
    "auto get_value(T t) {\n",
    "    return *t;\n",
    "}\n",
    "\n",
    "template <typename T,\n",
    "          std::enable_if_t<!std::is_pointer<T>{}>* = nullptr>\n",
    "auto get_value(T t) {\n",
    "    return t;\n",
    "}\n",
    "```\n",
    "\n",
    "Против `if constexpr`:\n",
    "\n",
    "```c++\n",
    "template <typename T>\n",
    "auto get_value(T t) {\n",
    "    if constexpr (std::is_pointer_v<T>)\n",
    "        return *t;\n",
    "    else\n",
    "        return t;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример 2**: Упрощение tag dispatching:\n",
    "\n",
    "Вариант реализации `get_value` через tag dispatching (вариант через тэг как доп. неиспользуемый аргумент переменного типа):\n",
    "\n",
    "```c++\n",
    "template <typename T>\n",
    "auto get_value(T t, std::true_type) {\n",
    "    return *t;\n",
    "}\n",
    "\n",
    "template <typename T>\n",
    "auto get_value(T t, std::false_type) {\n",
    "    return t;\n",
    "}\n",
    "\n",
    "template <typename T>\n",
    "auto get_value(T t) {\n",
    "    return get_value(t, std::is_pointer<T>{}); \n",
    "}\n",
    "```\n",
    "\n",
    "Против `if constexpr`:\n",
    "\n",
    "```c++\n",
    "template <typename T>\n",
    "auto get_value(T t) {\n",
    "    if constexpr (std::is_pointer_v<T>)\n",
    "        return *t;\n",
    "    else\n",
    "        return t;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример 3:** Упрощение рекурсивных variadic templates:\n",
    "\n",
    "```c++\n",
    "sum<5, 3, 2>() == 10;\n",
    "```\n",
    "\n",
    "Пример суммы `n` чисел через рекурсивные шаблоны и свёртки\n",
    "    \n",
    "```c++\n",
    "template <int N>\n",
    "int sum() {\n",
    "    return N;\n",
    "}\n",
    "\n",
    "template <int N1, int N2, int... Ns>\n",
    "int sum() {\n",
    "    return N1 + sum<N2, Ns...>();\n",
    "}\n",
    "```\n",
    "\n",
    "Пример через `if constepxr`\n",
    "\n",
    "```c++\n",
    "template <int N, int... Ns>\n",
    "int sum() {\n",
    "    if constexpr (sizeof...(Ns) == 0)\n",
    "        return N;\n",
    "    else\n",
    "        return N + sum<Ns...>();\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример 4**: Упрощение structured bindings для классов.\n",
    "\n",
    "Для структур structured bindings работает из коробки:\n",
    "\n",
    "```c++\n",
    "struct Point\n",
    "{\n",
    "    float x;\n",
    "    float y;\n",
    "};\n",
    "\n",
    "int main()\n",
    "{\n",
    "    std::vector<Point> polyline { ... };\n",
    "    auto [px, py] = polyline.front();\n",
    "    std::cout << px << \" \" << py;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Но он не работает для классов, где поля упрятаны в `private`:\n",
    "\n",
    "```c++\n",
    "class Person\n",
    "{\n",
    "private:\n",
    "    std::string name;\n",
    "    std::string surname;\n",
    "    int age;\n",
    "    \n",
    "public:\n",
    "    ...;\n",
    "};\n",
    "\n",
    "const auto [name, surname, age] = make_person(); // compile error\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Чтобы structured bindings завёлся для `private`-полей, нужно реализовать шаблонный метод `get`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вариант реализации через специализацию шаблонов:\n",
    "\n",
    "```c++\n",
    "class Person\n",
    "{\n",
    "private:\n",
    "    std::string name;\n",
    "    std::string surname;\n",
    "    int age;\n",
    "\n",
    "public:\n",
    "    Person() {}\n",
    "    \n",
    "    template <std::size_t N> friend auto get(const Person&);\n",
    "};\n",
    "\n",
    "namespace std {\n",
    "    template<> struct tuple_element<0, Person> { using type = std::string; };\n",
    "    template<> struct tuple_element<1, Person> { using type = std::string; };\n",
    "    template<> struct tuple_element<2, Person> { using type = int; };\n",
    "    template<> struct tuple_size<Person>: public integral_constant<size_t, 3> {};\n",
    "}\n",
    "\n",
    "template <>\n",
    "auto get<0>(const Person& p) {\n",
    "    return p.name;\n",
    "}\n",
    "\n",
    "template <>\n",
    "auto get<1>(const Person& p) {\n",
    "    return p.surname;\n",
    "}\n",
    "\n",
    "template <>\n",
    "auto get<2>(const Person& p) {\n",
    "    return p.age;\n",
    "}\n",
    "\n",
    "\n",
    "//\n",
    "// and finally!\n",
    "// \n",
    "const auto& [name, surname, age] = make_person();\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вариант реализации через `if constexpr`:\n",
    "\n",
    "```c++\n",
    "class Person\n",
    "{\n",
    "private:\n",
    "    std::string name;\n",
    "    std::string surname;\n",
    "    int age;\n",
    "\n",
    "public:\n",
    "    Person() {}\n",
    "    \n",
    "    template <std::size_t N> friend auto get(const Person&);\n",
    "};\n",
    "\n",
    "namespace std {\n",
    "    template<> struct tuple_element<0, Person> { using type = std::string; };\n",
    "    template<> struct tuple_element<1, Person> { using type = std::string; };\n",
    "    template<> struct tuple_element<2, Person> { using type = int; };\n",
    "    template<> struct tuple_size<Person>: public integral_constant<size_t, 3> {};\n",
    "}\n",
    "\n",
    "template <std::size_t N>\n",
    "auto get(const Person& p) {\n",
    "    if      constexpr (N == 0) return p.name;\n",
    "    else if constexpr (N == 1) return p.surname;\n",
    "    else if constexpr (N == 2) return p.age;\n",
    "    else throw std::out_of_range(\"Person class supports get<N> only for N in {0, 1, 2}\");\n",
    "}\n",
    "\n",
    "//\n",
    "// and finally!\n",
    "// \n",
    "const auto& [name, surname, age] = make_person();\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### C++20"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Дополнительно в `constexpr`-функциях разрешено:\n",
    "* иметь try-catch блок\n",
    "* иметь asm-блок\n",
    "* пользоваться union\n",
    "* вызывать виртуальные функции\n",
    "* dynamic_cast + typeid\n",
    "* new/delete"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "В таком коде компилятор теперь должен выдать ошибку, что происходит утечка:\n",
    "    \n",
    "```c++\n",
    "constexpr int foo()\n",
    "{\n",
    "    int *x = new int[3];\n",
    "    x[0] = 0;\n",
    "    x[1] = 1;\n",
    "    x[2] = 2;\n",
    "    return x[0] + x[1] + x[2];\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    constexpr int res = foo();\n",
    "    return res;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечание**: теперь в компилятор встроен инструмент поиска утечек памяти через constexpr!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А в таком коде компилятор найдёт undefined behavior:\n",
    "    \n",
    "```c++\n",
    "constexpr int foo()\n",
    "{\n",
    "    int *x = new int[3];\n",
    "    x[0] = 0;\n",
    "    x[1] = 1;\n",
    "    x[2] = 2;\n",
    "    const int res = x[0] + x[1] + x[2];\n",
    "    delete x;\n",
    "    return res;\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    constexpr int res = foo();\n",
    "    return res;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "А такой код скомпилируется успешно (когда выйдут компиляторы с поддержкой С++20) - закинуть пример на godbolt на clang (trunk) с опцией -std=c++2a, clang-9 ещё не умеет\n",
    "\n",
    "```c++\n",
    "constexpr int foo()\n",
    "{\n",
    "    int *x = new int[3];\n",
    "    x[0] = 0;\n",
    "    x[1] = 1;\n",
    "    x[2] = 2;\n",
    "    const int res = x[0] + x[1] + x[2];\n",
    "    delete[] x;\n",
    "    return res;\n",
    "}\n",
    "\n",
    "int main()\n",
    "{\n",
    "    constexpr int res = foo();\n",
    "    return res;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`constinit` - compiletime инициализация переменных. `constexpr` влечёт за собой `const`, т.е. переменную нельзя менять. Очень редко хочется, чтобы переменную (скорее, глобальную) проинициализировать в compiletime, а потом менять."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "constinit x = factorial(3);\n",
    "\n",
    "int main()\n",
    "{\n",
    "    x += 7;\n",
    "    return x;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример использования: инициализация счётчиков гистограмм в глобальных переменных, в которые код при выполнении будет накапливать хиты.\n",
    "\n",
    "```c++\n",
    "struct HistBucket\n",
    "{\n",
    "    std::string_view name;\n",
    "    std::uint64_t counter;\n",
    "};\n",
    "\n",
    "constinit std::array<HistBucket, 3> histograms {\n",
    "    {\"network_requests\", 0},\n",
    "    {\"network_failures\", 0},\n",
    "    {\"database_reads\", 0}\n",
    "};\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`consteval`-функции могут вызываться только в compile-time контексте."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "consteval int square(int i) {\n",
    "    return i * i;\n",
    "}\n",
    "\n",
    "constexpr int x = square(2); // ok\n",
    "int y = square(argc); // error\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Пример использования будет ниже."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`std::is_constant_evaluated()` - проверка, что находимся в compile-time контексте"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "constexpr int square(int i) {\n",
    "    if (std::is_constant_evaluated()) {\n",
    "        return i * i;  // slow code that allows compile-time\n",
    "    } else {\n",
    "        return magic_fast_square(i);  // fast code that disallowed in compile time\n",
    "    }\n",
    "}\n",
    "\n",
    "constexpr int x = square(2); // ok - compiletime, compiletime branch\n",
    "int y = square(argc); // ok, runtime, runtime branch\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### насколько compiletime медленнее runtime?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Возьмём пример с числами Фибоначи и добавим ничего не делающих вычислений, которые компилятор не может выкинуть в процессе оптимизации:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <iostream>\n",
    "\n",
    "constexpr std::uint64_t fib(std::uint64_t n)\n",
    "{\n",
    "    if (n <= 1)\n",
    "        return n;\n",
    "\n",
    "    for (std::uint64_t i = 1; i < 1000; ++i)\n",
    "        for (std::uint64_t j = 1; j < 1000; ++j)\n",
    "            if (i * i * i + j * j * j == n * n * n)\n",
    "                return 0;\n",
    "\n",
    "    return fib(n - 1) + fib(n - 2);\n",
    "}\n",
    "\n",
    "int main(int argc, char** argv)\n",
    "{\n",
    "    constexpr std::uint64_t res = fib(10);\n",
    "    std::cout << res << std::endl;\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Вот что на это говорит g++"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```bash\n",
    "$ g++ --version\n",
    "g++ (Ubuntu 7.4.0-1ubuntu1~18.04.1) 7.4.0\n",
    "\n",
    "$ time g++ main_constexpr.cpp\n",
    "\n",
    "real    0m19,215s\n",
    "user    0m18,914s\n",
    "sys     0m0,289s\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "19 секунд компиляции"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Что на это скажет clang?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```bash\n",
    "$ clang++-8 --version\n",
    "clang version 8.0.0-3~ubuntu18.04.1 (tags/RELEASE_800/final)\n",
    "\n",
    "$ time clang++-8 main_constexpr.cpp\n",
    "main_constexpr.cpp:19:29: error: constexpr variable 'res' must be initialized by a constant expression\n",
    "    constexpr std::uint64_t res = fib(10);\n",
    "                            ^     ~~~~~~~\n",
    "main_constexpr.cpp:11:13: note: constexpr evaluation hit maximum step limit; possible infinite loop?\n",
    "            if (i * i * i + j * j * j == n * n * n)\n",
    "            ^\n",
    "main_constexpr.cpp:14:12: note: in call to 'fib(9)'\n",
    "    return fib(n - 1) + fib(n - 2);\n",
    "           ^\n",
    "main_constexpr.cpp:19:35: note: in call to 'fib(10)'\n",
    "    constexpr std::uint64_t res = fib(10);\n",
    "                                  ^\n",
    "1 error generated.\n",
    "\n",
    "real    0m4,276s\n",
    "user    0m4,215s\n",
    "sys     0m0,041s\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Отказ от компиляции через 4 секунды с ошибкой: слишком много времени проведено в constexpr-вычислениях. Но clang-у можно передать опцию: компилируй подольше, не бойся:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```bash\n",
    "$ time clang++-8 main_constexpr.cpp  -fconstexpr-steps=900000000\n",
    "\n",
    "real    5m38,889s\n",
    "user    5m38,815s\n",
    "sys     0m0,042s\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Сделаем те же вычисления в runtime:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "#include <iostream>\n",
    "\n",
    "constexpr std::uint64_t fib(std::uint64_t n)\n",
    "{\n",
    "    if (n <= 1)\n",
    "        return n;\n",
    "\n",
    "    for (std::uint64_t i = 1; i < 1000; ++i)\n",
    "        for (std::uint64_t j = 1; j < 1000; ++j)\n",
    "            if (i * i * i + j * j * j == n * n * n)\n",
    "                return 0;\n",
    "\n",
    "    return fib(n - 1) + fib(n - 2);\n",
    "}\n",
    "\n",
    "int main(int argc, char** argv)\n",
    "{\n",
    "    volatile std::uint64_t n = 10;\n",
    "    std::cout << fib(n) << std::endl;\n",
    "    return 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "что скажет gcc?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```bash\n",
    "$ g++ main_constexpr_runtime.cpp && time ./a.out\n",
    "55\n",
    "\n",
    "real    0m0,265s\n",
    "user    0m0,261s\n",
    "sys     0m0,004\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "clang?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```bash\n",
    "$ clang++-8 main_constexpr_runtime.cpp && time ./a.out\n",
    "55\n",
    "\n",
    "real    0m0,274s\n",
    "user    0m0,270s\n",
    "sys     0m0,004s\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Итого**:\n",
    "\n",
    "|       ~     | gcc       |   clang   |\n",
    "|:------------|:---------:|:---------:|\n",
    "|compiletime  |   19 sec  |   339 sec |\n",
    "|runtime      |   0.3 sec |   0.3 sec |\n",
    "\n",
    "Результаты будут зависеть от железки и алгоритма, но в целом стоит иметь ввиду, что compiletime пока что на 2 порядка медленее, чем runtime.\n",
    "\n",
    "В рамках WG комитета стандартизации есть обсуждения как исправить такой разрыв, но принципиально сложно уйти от интерпретации, т.к. компилятор обязан ловить UB в compile-time вычислениях."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### как тестировать constexpr-функции"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Можно как и обычные функции. Но есть ещё вариант: `static_assert`-ами"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "constexpr int fib(int n)\n",
    "{\n",
    "    if (n <= 1)\n",
    "        return n;\n",
    "    return fib(n - 1) + fib(n - 2);\n",
    "}\n",
    "\n",
    "// boundary cases\n",
    "static_assert(fib(0) == 0);\n",
    "static_assert(fib(1) == 1);\n",
    "\n",
    "// happy path\n",
    "static_assert(fib(10) == 55);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечания**:\n",
    "* такие `static_assert`-тесты категорически не рекомендуется помещать в хедеры, иначе компилятор будет гонять эти тесты на каждое включение хедера\n",
    "* прелесть в том, что если копиляция проходит, значит, проходят и тесты\n",
    "* можно писать тесты прямо под кодом реализации (как это делается в других языках), и это не даст оверхеда на бинарный файл"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### constexpr in practice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример (hardcore)**: Порверка строк на регулярное выражение.\n",
    "\n",
    "* Выражение известно во время компиляции.\n",
    "* Проверяемые строки не известны\n",
    "* Компилятор на этапе компиляции генерирует конечный автомат, проверяющий регулярки. Т.к. КА известен на этапе компиляции, его можно заоптимизировать до безобразия.\n",
    "\n",
    "Доклад Hana Dusikova на cpprussia 2019 (дать ссылку, когда будет доступен доклад).\n",
    "Пока что показать [слайды с результатами](https://compile-time.re/cpprussia-piter/slides/#/13/2/6).\n",
    "\n",
    "Исходные коды:\n",
    "https://github.com/hanickadot/compile-time-regular-expressions (показать README)\n",
    "\n",
    "\n",
    "Вариант использования: проверка, что строка - корректный email. RE на email известен во время компиляции."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример (hardcore)**: проверка текста на соответствие грамматике (например, LL(1)) - грамматика вывода известна на этапе компиляции.\n",
    "\n",
    "Вариант использования: парсеры для языков программирования как часть компиляторов."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример:** user literals (since C++11)\n",
    "\n",
    "```c++\n",
    "constexpr double operator\"\" _deg(double deg)\n",
    "{\n",
    "    return deg * 3.14159265358979323846264L / 180;\n",
    "}\n",
    "\n",
    "constexpr double operator\"\" _mm(double value)\n",
    "{\n",
    "    return value / 1000.0;\n",
    "}\n",
    "\n",
    "constexpr double operator\"\" _cm(double value)\n",
    "{\n",
    "    return value / 100.0;\n",
    "}\n",
    "\n",
    "constexpr double operator\"\" _inch(double value)\n",
    "{\n",
    "    return value * 0.0254;\n",
    "}\n",
    "\n",
    "// usage:\n",
    "constexpr auto min_sphere_size = 2_mm;\n",
    "constexpr auto angle_step  = 3_deg;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример**: проверки программиста (пока нет C++23 и compile-time интроспекции)\n",
    "\n",
    "```c++\n",
    "// DebugFlags.h\n",
    "enum class DebugFlag\n",
    "{\n",
    "    VisualizeAlgorithm_1 = 0,\n",
    "    VisualizeAlgorithm_2,\n",
    "    VisualizeAlgorithm_3,\n",
    "    VisualizeAlgorithm_4\n",
    "};\n",
    "\n",
    "bool isDebugFlagEnabled(DebugFlag flag);\n",
    "\n",
    "\n",
    "// DebugFlags.cpp\n",
    "\n",
    "const std::array<std::string_view, 4> registry_names = {\n",
    "    \"VisualizeAlgorithm_1\",\n",
    "    \"VisualizeAlgorithm_2\",\n",
    "    \"VisualizeAlgorithm_3\",\n",
    "    \"VisualizeAlgorithm_4\"\n",
    "};\n",
    "\n",
    "bool isDebugFlagEnabled(DebugFlag flag) {\n",
    "    return getRegistryValue(registry_names[flag]) != 0;\n",
    "}\n",
    "```\n",
    "\n",
    "*Замечания*:\n",
    "1. очень не хочется вытаскивать `registry_names` в хедер, т.к. это, по сути, внутренняя информация, и внешнему коду про неё знать не надо, и компилировать не надо.\n",
    "2. но надо как-то гарантировать, что кол-во флагов совпадает с размером `registry_names`. Сейчас мы можем посчитать руками, но вдруг кто-то умный поменяет enum, а про имена забудет?\n",
    "\n",
    "Вариант (далёк от идеала, но интроспекция пока в процессе стандартизации):\n",
    "\n",
    "```c++\n",
    "// DebugFlags.h\n",
    "enum class DebugFlag\n",
    "{\n",
    "    VisualizeAlgorithm_1 = 0,\n",
    "    VisualizeAlgorithm_2,\n",
    "    VisualizeAlgorithm_3,\n",
    "    VisualizeAlgorithm_4,\n",
    "    FlagsCount  // <--------- NOTE: always last, it is common in C++\n",
    "};\n",
    "\n",
    "bool isDebugFlagEnabled(DebugFlag flag);\n",
    "\n",
    "\n",
    "// DebugFlags.cpp\n",
    "\n",
    "constexpr std::array<std::string_view, 4> registry_names = {\n",
    "    \"VisualizeAlgorithm_1\",\n",
    "    \"VisualizeAlgorithm_2\",\n",
    "    \"VisualizeAlgorithm_3\",\n",
    "    \"VisualizeAlgorithm_4\"\n",
    "};\n",
    "// проверим, что нужное число имён есть\n",
    "static_assert(static_cast<int>(DebugFlag::FlagsCount) == 4,\n",
    "              \"Did you forget to add registry name to debug flag?\");\n",
    "\n",
    "// проверим, что имена уникальны\n",
    "consteval bool areAllNamesUnique()\n",
    "{\n",
    "    for (int i = 0; i < static_cast<int>(DebugFlag::FlagsCount); ++i)\n",
    "        if (std::count(registry_names.begin(), registry_names.end(), registry_names[i]) != 1)\n",
    "            return false;\n",
    "    return true;\n",
    "}\n",
    "static_assert(areAllNamesUnique(),\n",
    "              \"Did you make just a copy-paste of registry name? Names must be unique\");\n",
    "\n",
    "bool isDebugFlagEnabled(DebugFlag flag) {\n",
    "    return getRegistryValue(registry_names[flag]) != 0;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Резюме:**\n",
    "* compile-time вычисления позволяют убрать вычисления из runtime, но:\n",
    "    * все входные данные должны быть известны на этапе компиляции\n",
    "    * код, который позволено выполнять в compile-time, ограничен по возможностям\n",
    "* До С++11 весь compile-time был в метапрограммировании, с С++11 он начинает развиваться.\n",
    "* У вычислений есть 2 контекста: runtime && compiletime\n",
    "    * обычная функция - runtime only\n",
    "    * `constexpr`-функция - runtime && compiletime (зависит от вызова) (since C++11)\n",
    "    * `consteval`-функция - compiletime only (since C++20)\n",
    "* Класс допустимых `constexpr` вычислений растёт с развитием стандарта, и ещё есть к чему стремиться\n",
    "* `constexpr`-вычисления медленные, т.к. компилятор интерпретирует код\n",
    "* `constexpr`-вычисления позволяют отлавливать UB (since C++11) и утечки (since C++20). Если компилятор в процессе интерпретации встречает UB, он завершается с ошибкой.\n",
    "    * Надо писать compile-time тесты (`static_assert` в помощь)\n",
    "* `if constexpr` позволяет упростить шаблонный код (since C++17)\n",
    "* `constinit` - для compile-time инициализации изменяемых переменных (since C++20)\n",
    "* В С++23 обещают compile-time интроспекцию кода."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
